package 链表;

public class Demo04 {
    /*
    * 硬来 不借助任何技巧(low)
    * */
    static class Solution {
        public Node copyRandomList(Node head) {
            Node newHead = null;
            Node tail = null;
            Node cur = head;
            // 拷贝新链表
            while(cur != null){
                int value = cur.val;
                Node node = new Node(value);
                if(newHead == null){
                    newHead = node;
                    tail = node;
                }else{
                    tail.next = node;
                    tail = node;
                }
                cur = cur.next;
            }

            cur = head;
            Node cur2 = newHead;

            while(cur != null){
                if(cur.random != null){
                    Node tmp1 = head;
                    Node tmp2 = newHead;
                    while(tmp1 != null){
                        if(tmp1 == cur.random){
                            cur2.random = tmp2;
                            break;
                        }
                        tmp1 = tmp1.next;
                        tmp2 = tmp2.next;
                    }
                }
                cur = cur.next;
                cur2 = cur2.next;
            }

            return newHead;
        }
    }

    /*
    * 思路: 哈希+链表
    * */
}
